#include <iostream>
#include <vector>

using namespace std;
// 93.复原IP地址[中等]
// 给出一个数字字符串，为这个数字字符串加上三个点(.)，使其成为一个合法的IP地址，返回所有的合法IP地址。
//-如给定字符串“25525511135”
//-返回[“255.255.11.135”, ”255.255.111.35”]
void print_vec(const vector<string>& vec){
    for(const string& e: vec)
        cout << e << " ";
    cout << endl;
}
class Solution {
public:

    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<int> ip;
        dfs(s, 0, ip, res);
        return res;
    }

private:
    // ip保存了当前处理的一个地址，int的数组，最长4个元素；index表示当前处理的字符索引
    void dfs(const string &s, int index, vector<int> &ip, vector<string> &res) {
        // 递归终止条件：index搜索到s的末尾，并且ip里有4个元素(整数)
        if(index == s.size()) {
            if(ip.size() == 4)
                res.push_back(get_string(ip));
            return;
        }
        // 这里将处理第1个数字和其他数字分开，便于后续计算数字
        if(index == 0) {
            // 只有第1个字符可以为0，不用判断是否为0
            ip.push_back(s[0] - '0');
            dfs(s, index+1, ip, res);
        } else {
            // 计算出加入s[index]后代表的数字
            int next = ip.back() * 10 + (s[index] - '0');
            // ip.back()！=0就是判断每个部分不可以以0开头的；并且数字要小于255
            if(next <= 255 && ip.back() !=0 ) {
                ip.back() = next;
                dfs(s, index+1, ip, res);
//                cout<<"backtrack, ip = ";
//                print_ip(ip);
                ip.back() /= 10;    // 回溯，回退上一个index的数字
            }
            if(ip.size() < 4) {
                ip.push_back(s[index] - '0');
                dfs(s, index+1, ip, res);
                ip.pop_back();
            }
        }

    }
    // 将数字数组转换为一个字符串
    string get_string(const vector<int> &ip) {
        string res = to_string(ip[0]);
        for(int i = 1; i < ip.size(); i++)
            res += "." + to_string(ip[i]);
        return res;
    }
    void print_ip(const vector<int>& ip){
        for(const int& e: ip)
            cout << e << ".";
        cout << endl;
    }
};



int main() {
    string s1 = "25525511135";
    print_vec(Solution().restoreIpAddresses(s1));
    // 255.255.111.35 255.255.11.135

    string s2 = "1";
    print_vec(Solution().restoreIpAddresses(s2));
    // empty

    string s3 = "010010";
    print_vec(Solution().restoreIpAddresses(s3));
    // 0.10.0.10 0.100.1.0

    return 0;
}
